#include "headfiles.h"

using namespace std;

bool findIntPairs(int *array, int n, int sum) {
    if (array == NULL ||
        n <= 0) {
        cout << "Invalid input argument!" << endl;
        return false;
    }

    map<int, bool> num_map;
    int i;
    for (i = 0; i < n; i++) {
        num_map[array[i]] = false;
    }

    for (i = 0; i < n; i++) {
        int ret = sum - array[i];
        if (num_map[array[i]] == false) {
            map<int, bool>::iterator it = num_map.find(ret);
            if (it != num_map.end()) {
                cout << "(" << array[i] << ", " << ret << ")" << endl;
                num_map[ret] = true;
            }
            num_map[array[i]] = true;
        }
    }

    return true;
}

// Assume the input array is sorted in ascending order
bool findIntPairs1(int *array, int n, int sum) {
    if (array == NULL ||
        n <= 0) {
        cout << "Invalid input argument!" << endl;
        return false;
    }

    int start = 0;
    int end = n - 1;

    while (start <= end) {
        if (array[start] + array[end] < sum) {
            ++start;
        }
        else if (array[start] + array[end] > sum) {
            --end;
        }
        else {
            cout << "(" << array[start] << ", " << array[end] << ")" << endl;
            while (start < n - 1) {
                if (array[start] == array[start+1]) {
                    ++start;
                }
                else {
                    break;
                }
            }
            ++start;

            while (end > 0) {
                if (array[end] == array[end - 1]) {
                    --end;
                }
                else {
                    break;
                }
            }
            --end;
        }
    }

    return false;
}

